package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.ArrayList;
import java.util.List;

public class 杨辉三角 {


    public List<List<Integer>> generate(int numRows) {
         int[][] dp = new int[numRows][numRows];

        for (int i = 0; i < numRows; i++) {
            dp[i][i]  = 1;
        }
        for (int i = 0; i < numRows; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i < numRows; i++) {
            for (int j = 1; j < numRows; j++) {
                if (i==j){
                    continue;
                }
                if (dp[i-1][j-1] ==0 && dp[i-1][j] ==0) {
                    continue;
                }
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> list  =  new ArrayList<>();
            for (int j = 0; j < numRows; j++) {
                if (dp[i][j] == 0) continue;
                list.add(dp[i][j]);
            }
            res.add(list);
        }


        return res;
    }

    public static void main(String[] args) {
        杨辉三角 obj = new 杨辉三角();
        obj.generate(5);


    }

}
